import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 05
 * Time: 21:50
 */
//牛客 没有重复项数字的全排列
public class Solution6 {
    ArrayList<ArrayList<Integer>> ret;
    ArrayList<Integer> path;
    boolean[] check;
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[num.length];
        Arrays.sort(num);
        dfs(num);
        return ret;
    }
    private void dfs(int[] num) {
        if(path.size() == num.length) {
            ret.add(new ArrayList<>(path));//注意add的是new ArrayList<>(path)
            return ;
        }
        for (int i = 0; i < num.length; i++) {
            if(check[i] == false) {//check数组用来实现剪枝
                path.add(num[i]);
                check[i] = true;
                dfs(num);//每递归到下一层，path就会add多一个元素
                //回溯 回溯完成之后再恢复现场(也可以恢复现场之后再回溯，但这样写法会麻烦一点)
                check[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}
